package _11_整理题目._1_链表指针._合并链表;

import org.junit.Test;
import util.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 *
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * 思路一：顺序合并
 *      每次合并前连个链表，直至合并完所有的
 * 思路二：分支合并
 *      先合并 0 和 1，   2 和 3，    4 和 5 ，再向上合并
 * 思路三：使用优先队列
 *      维护 k 个链表最前面的元素，每次 poll 一个最小的，并将其后元素放入
 *
 */
public class _03_合并多个有序链表 {

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>((v1, v2)-> v1.val-v2.val);
        for (ListNode listNode : lists) {
            if (listNode != null) queue.offer(listNode);
        }
        ListNode fake = new ListNode(0);
        ListNode point = fake;
        while (!queue.isEmpty()) {
            ListNode node = queue.poll();
            point.next = node;
            point = point.next;
            if (node.next != null) queue.offer(node.next);
        }
        return fake.next;
    }

    @Test
    public void main() {
        ListNode[] array = new ListNode[4];
        array[0] = ListNode.getListFromArray(new Integer[]{1,4,6});
        array[1] = ListNode.getListFromArray(new Integer[]{});
        array[2] = ListNode.getListFromArray(new Integer[]{2,5});
        array[3] = ListNode.getListFromArray(new Integer[]{1,3});
        ListNode head = mergeKLists(array);
        ListNode.printList(head);
    }
}
